[LeetCode] 53 - Maximum Subarray

題意

求連續一段區間相加最大的值。

解法

最少需要選一個，要特別注意全都是負值的情況。

心得

搞了老半天才知道格式是什麼，原來不用輸出返回即可。

程式

class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		int max_sum = -999999 , sum = 0 ;
		for ( int i = 0 ; i < nums.size() ; i ++ ){
			if ( sum > 0 ) 
				sum += nums[i] ;
			else 
				sum = nums[i] ;
			if ( sum > max_sum )  
				max_sum = sum ;
		}
		return max_sum ;
	}
};